package structures;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import org.apache.commons.lang.ArrayUtils;


public class Graph {
	public State[] vertexes;
	public List<Integer> order = new ArrayList<Integer>();
	
	public static Graph getFromAutomate(AutomateBuhi automate)
	{
		Graph result = new Graph();
		result.vertexes = automate.startState.getStatesArray();
		Arrays.sort(result.vertexes);
		
		for (int i=0;i!=result.vertexes.length;++i)
		{
			result.vertexes[i].index = i;
			result.vertexes[i].marked = false;
		}
		return result;
	}
	
	public boolean containsStrongComponents()
	{
		Stack<Integer> dfs = new Stack<Integer>();
		for (State vertex : vertexes)
		{
			if (vertex.marked)
				continue;
			dfs(vertex);
		}
		for (State vertex : vertexes)
		{
			vertex.marked = false;
		}
		State[] newVertexes = trans();
		Object[] objOrder  = order.toArray();
		int[] newOrder = new int[objOrder.length];
		for (int i=0;i!=newOrder.length;++i)
		{
			newOrder[i] = (Integer) objOrder[i];
		}
		
		ArrayUtils.reverse(newOrder);
		int colour = 0;
				
		for (int i=0;i!=newOrder.length;++i)
		{
			State vertex = newVertexes[newOrder[i]];
			if (vertex.marked)
				continue;
			dfs2(vertex,colour);
			++colour;
		}
		
		for (int k=0;k!=colour;++k)
		{
			List<State> coloredStates = new ArrayList<State>();
			for (int i = 0; i!= newVertexes.length;++i)
			{
				if (newVertexes[i].colour==k)
				{
					coloredStates.add(newVertexes[i]);
				}
			}
			
			if (coloredStates.size()==1)
			{
				if (!coloredStates.get(0).isFinalState)
					continue;
				Object[] states = coloredStates.get(0).getEdges().keySet().toArray();
				if (states.length == 0)
					return false;
				for (Object direction : states)
				{
					if ((State)direction == coloredStates.get(0))
						return true;
				}
			}else{
				for (State state : coloredStates)
				{
					if (state.isFinalState)
						return true;
				}
			}
		}
				
		return false;
	}
	
	private State[] trans()
	{
		State[] result = new State[vertexes.length];
		for (int i = 0; i!= result.length;++i)
		{
			result[i] = new State();
			result[i].index = i;
			result[i].isFinalState = vertexes[i].isFinalState;
			result[i].isStartState = vertexes[i].isStartState;
			result[i].marked = false;
		}
		for (int i = 0; i!= result.length;++i)
		{
			for (Map.Entry<State, Set<String>> entry : vertexes[i].getEdges().entrySet())
			{
				result[entry.getKey().index].addEdge(result[i], (String)entry.getValue().toArray()[0]);
			}
		}
		return result;
	}
	
	private void dfs(State vertex)
	{
		vertex.marked = true;
		for (State edge : vertex.getEdges().keySet())
		{
			if (edge.marked)
				continue;
			dfs(edge);
		}
		order.add(vertex.index);
	}
	
	private void dfs2(State vertex, int colour)
	{
		vertex.marked = true;
		for (State edge : vertex.getEdges().keySet())
		{
			if (edge.marked)
				continue;
			dfs2(edge,colour);
		}
		vertex.colour = colour;
	}
}